package com.shawn.algorithm.divideconquer;

/**
 * 利用分治算法求一组数据的逆序对个数
 */
public class ReverseCount {

	private int num = 0;

	public void count(int[] a) {
		mergeCount(a, 0, a.length - 1);
	}

	public void mergeCount(int[] a, int p, int r) {
		if (p >= r) {
			return;
		}
		int q = p + ((r - p) >> 1);
		mergeCount(a, p, q);
		mergeCount(a, q + 1, r);
		merge(a, p, q, r);
	}

	private void merge(int[] a, int p, int q, int r) {
		int[] tmp = new int[r - p + 1];
		int i = p;
		int j = q + 1;
		int k = 0;

		while (i <= q && j <= r) {
			if (a[i] <= a[j]) {
				tmp[k++] = a[i++];
			} else {
				num += (q - i + 1);
				tmp[k++] = a[j++];
			}
		}
		while (i <= q) {
			tmp[k++] = a[i++];
		}

		while (j <= r) {
			tmp[k++] = a[j++];
		}

		for (int m = 0; m < r - p; m++) {
			a[p + m] = tmp[m];
		}
	}
}
